package com.zlk.algorithm.huawei.leetcode.matrix;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName Code14_searchMatrix
 * @description:
 * @author: slfang
 * @create: 2025-01-06 15:59
 * @Version 1.0
 **/
public class Code14_searchMatrix {

//    从最右上角的元素开始找，如果这个元素比target大，则说明找更小的，往左走；如果这个元素比target小，则说明应该找更大的，往下走。
//    画个图看代码就很容易理解，总之就是从右上角开始找，如果矩阵的元素小了就往下走，如果矩阵元素大了就往左走。如果某个时刻相等了，
//    就说明找到了，如果一直走出矩阵边界了还没找到，则说明不存在。
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length < 1 || matrix[0].length < 1){
            return false;
        }
        //起点为最右上角的元素
        int row = 0, col = matrix[0].length - 1;
        //判断当前数组元素和target，如果当前大于target，往左走；小与target，往下走
        while(row < matrix.length && col >= 0){
            if(matrix[row][col] < target){
                row++;
            }else if(matrix[row][col] > target){
                col--;
            }else{
                return true;
            }
        }
        //走出边界了还没找到，说明不存在，返回false
        return false;
    }

    public boolean searchMatrix1(int[][] matrix, int target) {
        int i = 0;
        int j = 0;
        int n = matrix.length;
        int m = matrix[0].length;
        while (i<n&&j<m){
            if(findTargert(i,m-1,i,"row",matrix,target)||
                    findTargert(i,n-1,j,"col",matrix,target)){
                return true;
            }
            i++;
            j++;
        }
        return false;
    }
    private boolean findTargert(int l, int r, int i, String type, int[][] matrix, int target) {
        boolean ans=false;
        int mid ;
        while (l<=r){
            mid = l+(r-l)/2;
            if("row".equals(type)){
                if(matrix[i][mid]<target){
                    l =mid+1;
                }else if(matrix[i][mid]>target){
                    r=mid-1;
                }else{
                    ans=true;
                    break;
                }
            }else{
                if(matrix[mid][i]<target){
                    l =mid+1;
                }else if(matrix[mid][i]>target){
                    r=mid-1;
                }else{
                    ans=true;
                    break;
                }
            }
        }
        return ans;
    }


    @Test
    public void test(){
//        int[][] martix = new int[][]{{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
//        searchMatrix(martix,5);
        int[][] marrix = new int[][]{{1,3,5,7,9},{2,4,6,8,10},{11,13,15,17,19},{12,14,16,18,20},{21,22,23,24,25}};
        searchMatrix(marrix,13);
    }
}
